/**
 * @author tmh
 * @date 2024/10/24 16:16
 * @description 使用环检测算法
 */
public class T287寻找重复数2 {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        slow=nums[slow];
        fast=nums[nums[fast]];
        //找相遇的地方
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        //找成环的起点
        int pre = 0;
        while (pre != slow) {
            pre = nums[pre];
            slow = nums[slow];
        }
        return pre;
    }
}
